package _back_tracking

import org.junit.Assert
import org.junit.Test

/**
 * 1079. 活字印刷
 *
 * https://leetcode.cn/problems/letter-tile-possibilities/description
 *
 * ```
 * 你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
 * 注意：本题中，每个活字字模只能使用一次。
 *
 *
 * 示例 1：
 * 输入："AAB"
 * 输出：8
 * 解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

 * 示例 2：
 * 输入："AAABBC"
 * 输出：188
 *
 * 示例 3：
 * 输入："V"
 * 输出：1
 *
 *
 * 提示：
 * 1 <= tiles.length <= 7
 * tiles 由大写英文字母组成
 * ```
 */
class leetcode_1079 {
    @Test
    fun test_1() {
        val result = numTilePossibilities("AAB")
        val expected = 8
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_2() {
        val result = numTilePossibilities("AAABBC")
        val expected = 188
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_3() {
        val result = numTilePossibilities("V")
        val expected = 1
        Assert.assertEquals(expected, result)
    }

    fun numTilePossibilities(tiles: String): Int {
        val charArray = tiles.toCharArray()
        charArray.sort()
        collect(charArray, "", BooleanArray(tiles.length))
        return count
    }

    var count: Int = 0
    fun collect(array: CharArray, path: String, used: BooleanArray) {
        // 1 确定函数参数以及返回值

        // 2 确定终止条件
        // 终止条件
        if (array.size == 0) {
            return
        }
        // 收集结果
        if (path.length > 0 && path.length <= array.size) {
            println("path=$path")
            count++;
        }

        // 3 确定单层循环的递归逻辑
        for (i in 0 until array.size) {
            // 处理节点
            if (used[i] == true) { // 树枝去重
                continue
            }
            if (i > 0 && array[i] == array[i - 1] && used[i - 1] == false) { // 树层去重
                continue
            }
            used[i] = true

            // 递归
            collect(array, path + array[i], used)

            // 回溯
            used[i] = false

            // 4 剪枝？
            // 5 去重？
        }
    }

    fun numTilePossibilities2(tiles: String): Int {
        val path: ArrayList<Char> = ArrayList()
        val chars = tiles.toCharArray()
        chars.sort()
        count = 0
        collect(chars, BooleanArray(tiles.length), path)
        return count
    }

    fun collect(chars: CharArray, used: BooleanArray, path: ArrayList<Char>) {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        // 终止条件
        if (path.size > chars.size) {
            return
        }
        // 收集结果
        if (path.size > 0) {
            println(String(path.toCharArray()))
            count++
        }
        // 3 确定单层循环的处理逻辑
        for (i in 0 until chars.size) {
            // 处理节点
            if (used[i] == true) {
                continue
            }
            if (i > 0 && chars[i] == chars[i - 1] && used[i - 1] == false) {
                continue
            }
            used[i] = true
            path.add(chars[i])

            // 递归
            collect(chars, used, path)

            // 回溯
            used[i] = false
            path.removeAt(path.size - 1)

            // 去重？剪枝？
        }
    }
}